# !/usr/bin/python
# -*- coding: utf-8 -*-
'''
@File    :   13_mergesort.py
@Time    :   2021/04/02 14:39:39
@Author  :   Qingxiang Zhang
@Version :   1.0
@Contact :   344285081@qq.com
@Desc    :   归并算法
@Software:    Vscode
'''
'''
归并算法：每次一直拆分，一直一直的拆分，拆分之后，
在向上面上炫，两两合并，合并排序，
'''
def merge_sort(aList):
    n = len(aList)
    mid = n//2
    if n <= 1:
        return aList
    # 将两边进行拆分
    left_li = merge_sort(aList[:mid])
    right_li = merge_sort(aList[mid:])


    left_pointer = 0
    right_pointer =0
    result =[]
    while left_pointer < len(left_li) and right_pointer < len(right_li):
        if left_li[left_pointer] < right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer += 1
        else:
            result.append(right_li[right_pointer])
            right_pointer +=1

    result += left_li[left_pointer:]
    result += right_li[right_pointer:]
    return result


if __name__=="__main__":
        li = [3,7,9,5,1,4]
        print(li)
        sort_li = merge_sort(li)
        print(sort_li)